home *** CD-ROM | disk | FTP | other *** search
/ The X-Philes (2nd Revision) / The X-Philes Number 1 (1995).iso / xphiles / hp48hor2 / rand.doc < prev    next >
Text File  |  1995-03-31  |  2KB  |  70 lines
  1. How RAND Works 
  2. by Steve VanDevender & Detlef Mueller 
  3.  
  4. (Comp.sys.hp48) 
  5. Item: 1661 by jollie@zambini.cs.uiowa.edu [Jeffrey C. Ollie] 
  6. Subj: HP's RAND algorithm 
  7. Date: 04 Sep 1992 
  8.  
  9. I just got my 48SX, and I love it! But, I was wondering what algorithm 
  10. HP used for the random number generator. I'm hoping that it is a 
  11. prime modulus multiplicative linear conguential generator (I'm not 
  12. making this up) with a=16807 and m=2^31 - 1. I've written one of my own, 
  13. but would prefer to use the built in RAND. 
  14.  
  15. Jeff Ollie 
  16. jollie@zambini.cs.uiowa.edu "The Happy User" 
  17.  
  18. ---------- 
  19. Resp: 1 of 2 by stevev@miser.uoregon.edu [Steve VanDevender] 
  20. Date: 05 Sep 1992 
  21.  
  22. The HP 48 uses a multiplicative linear congruential generator (I 
  23. know you're not making it up) but not the particular one you 
  24. speak of.  It uses the formula 
  25.  
  26. R(n+1) = R(n) * 2851130928467 (mod 10^15) 
  27.  
  28. to generate a 15 decimal digit internal seed.  The random number 
  29. returned is R(n+1) / 10^15 rounded to 12 decimal digits. 
  30.  
  31. The random number seed R(n) is stored in BCD at #706A4.  If the 
  32. seed is 0, then the seed is reset to 999500333083533. 
  33.  
  34. This information was obtained by disassembling the system RPL 
  35. routine %RAN, a primitive code object at #2AFC2. 
  36. -- 
  37. Steve VanDevender       stevev@greylady.uoregon.edu 
  38.  
  39. ---------- 
  40. Resp: 2 of 2 by detlef@dmhh.hanse.de [Detlef Mueller] 
  41. Date: 06 Sep 1992 
  42.  
  43. Don't worry, RAND is based on a linear congruential method (see pg. 9 of 
  44. 'The Art of Computer Programming', Vol.2 by D.E. Knuth): 
  45.  
  46.     Xn+1 = (a * Xn + c) mod m 
  47.  
  48. where 
  49.     a = 2851130928467 
  50.     c = 0 
  51.     m = 1E15 
  52.  
  53. The intial value of X0 after a memory lost is 999500333083533. 
  54.  
  55. If you choose an X0 which isn't a multiple of 2 or 5 then you'll get a 
  56. period of 5E13 (see pg. 20 of above book - a mod 200 is 67). 
  57.  
  58. Bye, 
  59.         8-Detlef 
  60. -- 
  61.  
  62. [Note: Yes, 2851130928467 is a prime number.  999500333083533 factors 
  63.  into 3^2 * 19 * 5845031187623.  This computation was done with 
  64.  FCTR.LIB by Klaus Kalb, on Goodies Disk #8. Jeff wanted the modulus 
  65.  to be prime also, but since it's a power of 10, it's obviously not. 
  66.  The cycle is so huge, however, that it doesn't matter; if you were to 
  67.  generate 100 RAND's every second (that's about as fast as the 48 can 
  68.  go), it'd take more than 15,000 years for the cycle to start 
  69.  repeating!  This machine is fun to play with... -jkh-] 
  70.